﻿#define _CRT_SECURE_NO_WARNINGS 1
//快速选择算法（medium）:https://leetcode.cn/problems/kth-largest-element-in-an-array/description/
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        srand(time(NULL));
        return qsort(nums, k, 0, nums.size() - 1);
    }
    int qsort(vector<int>& nums, int k, int begin, int end)
    {
        if (begin == end)  return nums[end];
        int mid = getRandom(nums, begin, end);
        int left = begin - 1, right = end + 1, i = begin;
        while (i < right)
        {
            if (nums[i] == mid)
            {
                i++;
            }
            else if (nums[i] < mid)
            {
                swap(nums[++left], nums[i++]);
            }
            else
            {
                swap(nums[i], nums[--right]);
            }
        }
        //[begin,left] [left+1,right-1] [right,end]
        int a = left - begin + 1;
        int b = right - 1 - left - 1 + 1;
        int c = end - right + 1;
        if (c >= k)   //k
        {
            return qsort(nums, k, right, end);
        }
        else if (c + b >= k)   //k-c
        {
            return mid;
        }
        else        //k-b-c
        {
            return qsort(nums, k - c - b, begin, left);
        }
    }
    int getRandom(vector<int>& nums, int begin, int end)
    {
        int r = rand();
        int i = r % (end - begin + 1) + begin;
        return nums[i];
    }
};

//最⼩的 k 个数（medium）:https://leetcode.cn/problems/zui-xiao-de-kge-shu-lcof/
class Solution {
public:
    vector<int> inventoryManagement(vector<int>& stock, int cnt) {
        srand(time(NULL));
        sqort(stock, 0, stock.size() - 1, cnt);
        return { stock.begin(),stock.begin() + cnt };
    }
    void sqort(vector<int>& stock, int begin, int end, int k)
    {
        if (begin >= end)
        {
            return;
        }
        int key = getRandom(stock, begin, end);
        int left = begin - 1, right = end + 1, i = begin;
        while (i < right)
        {
            if (stock[i] == key)
            {
                i++;
            }
            else if (stock[i] < key)
            {
                swap(stock[++left], stock[i++]);
            }
            else
            {
                swap(stock[i], stock[--right]);
            }
        }
        //[begin,left] [left+1,right-1] [right,end]
        int a = left - begin + 1;
        int b = right - 1 - left - 1 + 1;
        int c = end - right + 1;
        if (a > k)
        {
            sqort(stock, begin, left, k);
        }
        else if (a + b >= k)
        {
            return;
        }
        else
        {
            if (a + b + c == k)
            {
                return;
            }
            sqort(stock, right, end, k - a - b);
        }
    }
    int getRandom(vector<int>& stock, int begin, int end)
    {
        int r = rand();
        int i = r % (end - begin + 1) + begin;
        return stock[i];
    }
};